SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Random sequence</title>

</head>

Random sequence

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr">The concept of a random sequence is essential in <a href="Probability_theory" title="Probability theory">probability theory</a> and <a href="Statistics" title="Statistics">statistics</a>. The concept generally relies on the notion of a <a href="Sequence" title="Sequence">sequence</a> of <a href="Random_variable" title="Random variable">random variables</a> and many statistical discussions begin with the words "let X1,...,Xn be independent random variables...". Yet as <a href="D._H._Lehmer" title="D. H. Lehmer">D. H. Lehmer</a> stated in 1951: "A random sequence is a vague notion... in which each term is unpredictable to the uninitiated and whose digits pass a certain number of tests traditional with statisticians".<a href="#cite_note-1">[1]</a>

<a href="Probability_axioms" title="Probability axioms">Axiomatic probability theory</a> deliberately avoids a definition of a random sequence.<a href="#cite_note-2">[2]</a> Traditional probability theory does not state if a specific sequence is random, but generally proceeds to discuss the properties of random variables and stochastic sequences assuming some definition of randomness. The <a href="Nicolas_Bourbaki" title="Nicolas Bourbaki">Bourbaki school</a> considered the statement "let us consider a random sequence" an <a href="Abuse_of_terminology" class="mw-redirect" title="Abuse of terminology">abuse of language</a>.<a href="#cite_note-3">[3]</a>

<div class="mw-heading mw-heading2"><h2 id="Early_history">Early history</h2></div>

<a href="%C3%89mile_Borel" title="Émile Borel">Émile Borel</a> was one of the first mathematicians to formally address randomness in 1909.<a href="#cite_note-4">[4]</a> In 1919 <a href="Richard_von_Mises" title="Richard von Mises">Richard von Mises</a> gave the first definition of <a href="Algorithmic_randomness" class="mw-redirect" title="Algorithmic randomness">algorithmic randomness</a>, which was inspired by the law of large numbers, although he used the term collective rather than random sequence. Using the concept of the <a href="Impossibility_of_a_gambling_system" title="Impossibility of a gambling system">impossibility of a gambling system</a>, von Mises defined an infinite sequence of zeros and ones as random if it is not biased by having the frequency stability property i.e. the frequency of zeros goes to 1/2 and every sub-sequence we can select from it by a "proper" method of selection is also not biased.<a href="#cite_note-5">[5]</a>

The sub-sequence selection criterion imposed by von Mises is important, because although 0101010101... is not biased, by selecting the odd positions, we get 000000... which is not random. Von Mises never totally formalized his definition of a proper selection rule for sub-sequences, but in 1940 <a href="Alonzo_Church" title="Alonzo Church">Alonzo Church</a> defined it as any <a href="Recursion#Functional_recursion" title="Recursion">recursive function</a> which having read the first N elements of the sequence decides if it wants to select element number N + 1. Church was a pioneer in the field of computable functions, and the definition he made relied on the <a href="Church_Turing_Thesis" class="mw-redirect" title="Church Turing Thesis">Church Turing Thesis</a> for computability.<a href="#cite_note-6">[6]</a> This definition is often called Mises–Church randomness.

<div class="mw-heading mw-heading2"><h2 id="Modern_approaches">Modern approaches</h2></div>

During the 20th century various technical approaches to defining random sequences were developed and now three distinct paradigms can be identified. In the mid 1960s, <a href="A._N._Kolmogorov" class="mw-redirect" title="A. N. Kolmogorov">A. N. Kolmogorov</a> and <a href="D._W._Loveland" class="mw-redirect" title="D. W. Loveland">D. W. Loveland</a> independently proposed a more permissive selection rule.<a href="#cite_note-7">[7]</a><a href="#cite_note-8">[8]</a> In their view Church's recursive function definition was too restrictive in that it read the elements in order. Instead they proposed a rule based on a partially computable process which having read any N elements of the sequence, decides if it wants to select another element which has not been read yet. This definition is often called Kolmogorov–Loveland stochasticity. But this method was considered too weak by Alexander Shen who showed that there is a Kolmogorov–Loveland stochastic sequence which does not conform to the general notion of randomness.

In 1966 <a href="Per_Martin-L%C3%B6f" title="Per Martin-Löf">Per Martin-Löf</a> introduced a new notion which is now generally considered the most satisfactory notion of <a href="Algorithmic_randomness" class="mw-redirect" title="Algorithmic randomness">algorithmic randomness</a>. His original definition involved measure theory, but it was later shown that it can be expressed in terms of <a href="Kolmogorov_complexity" title="Kolmogorov complexity">Kolmogorov complexity</a>. Kolmogorov's definition of a random string was that it is random if it has no description shorter than itself via a <a href="Universal_Turing_machine" title="Universal Turing machine">universal Turing machine</a>.<a href="#cite_note-9">[9]</a>

Three basic paradigms for dealing with random sequences have now emerged:<a href="#cite_note-10">[10]</a>

<dl><dd><ul><li>The frequency / measure-theoretic approach. This approach started with the work of Richard von Mises and Alonzo Church. In the 1960s Per Martin-Löf noticed that the sets coding such frequency-based stochastic properties are a special kind of <a href="Measure_zero" class="mw-redirect" title="Measure zero">measure zero</a> sets, and that a more general and smooth definition can be obtained by considering all effectively measure zero sets.</li></ul></dd></dl>

<dl><dd><ul><li>The complexity / compressibility approach. This paradigm was championed by A. N. Kolmogorov along with contributions from <a href="Leonid_Levin" title="Leonid Levin">Leonid Levin</a> and <a href="Gregory_Chaitin" title="Gregory Chaitin">Gregory Chaitin</a>. For finite sequences, Kolmogorov defines randomness of a binary string of length n as the entropy (or <a href="Kolmogorov_complexity" title="Kolmogorov complexity">Kolmogorov complexity</a>) normalized by the length n. In other words, if the Kolmogorov complexity of the string is close to n, it is very random; if the complexity is far below n, it is not so random. The dual concept of randomness is compressibility ‒ the more random a sequence is, the less compressible, and vice versa.</li></ul></dd></dl>

<dl><dd><ul><li>The predictability approach. This paradigm is due to <a href="Claus_P._Schnorr" title="Claus P. Schnorr">Claus P. Schnorr</a> and uses a slightly different definition of constructive <a href="Martingale_(probability_theory)" title="Martingale (probability theory)">martingales</a> than martingales used in traditional probability theory.<a href="#cite_note-11">[11]</a> Schnorr showed how the existence of a selective betting strategy implied the existence of a selection rule for a biased sub-sequence. If one only requires a recursive martingale to succeed on a sequence instead of constructively succeed on a sequence, then one gets the concept of recursive randomness. <a href="Yongge_Wang" title="Yongge Wang">Yongge Wang</a> showed<a href="#cite_note-12">[12]</a><a href="#cite_note-13">[13]</a> that recursive randomness concept is different from Schnorr's randomness concept.</li></ul></dd></dl>

In most cases, theorems relating the three paradigms (often equivalence) have been proven.<a href="#cite_note-14">[14]</a>

<ul><li><a href="Randomness" title="Randomness">Randomness</a></li>

<li><a href="History_of_randomness" title="History of randomness">History of randomness</a></li>

<li><a href="Random_number_generator" class="mw-redirect" title="Random number generator">Random number generator</a></li>

<li><a href="Seven_states_of_randomness" title="Seven states of randomness">Seven states of randomness</a></li>

<li><a href="Statistical_randomness" title="Statistical randomness">Statistical randomness</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li>Sergio B. Volchan <a rel="nofollow" class="external text" href="http://www.maa.org/programs/maa-awards/writing-awards/what-is-a-random-sequence">What Is a Random Sequence?</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20210427141355/http://www.maa.org/programs/maa-awards/writing-awards/what-is-a-random-sequence">Archived</a> 2021-04-27 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a> The American Mathematical Monthly, Vol. 109, 2002, pp. 46–63</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><a href="#cite_ref-1">^</a> "What is meant by the word Random" in Mathematics and common sense by Philip J. Davis 2006 <style data-mw-deduplicate="TemplateStyles:r1238218222">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>1-56881-270-1</bdi> pages 180-182

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> Inevitable Randomness in Discrete Mathematics by József Beck 2009 <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-8218-4756-2</bdi> page 44

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> Algorithms: main ideas and applications by Vladimir Andreevich Uspenskiĭ, Alekseĭ, Lʹvovich Semenov 1993 Springer <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-7923-2210-X</bdi> page 166

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> E. Borel, Les probabilites denombrables et leurs applications arithmetique Rend. Circ. Mat. Palermo 27 (1909) 247–271

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> Laurant Bienvenu "Kolmogorov Loveland Stochasticity" in STACS 2007: 24th Annual Symposium on Theoretical Aspects of Computer Science by Wolfgang Thomas <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>3-540-70917-7</bdi> page 260

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFChurch1940" class="citation journal cs1"><a href="Alonzo_Church" title="Alonzo Church">Church, Alonzo</a> (1940). <a rel="nofollow" class="external text" href="https://doi.org/10.1090%2FS0002-9904-1940-07154-X">"On the Concept of Random Sequence"</a>. Bull. Amer. Math. Soc. 46 (2): 130–136. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090%2FS0002-9904-1940-07154-X">10.1090/S0002-9904-1940-07154-X</a>.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> A. N. Kolmogorov, Three approaches to the quantitative definition of information Problems of Information and Transmission, 1(1):1–7, 1965.

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> D.W. Loveland, A new interpretation of von Mises' concept of random sequence Z. Math. Logik Grundlagen Math 12 (1966) 279–294

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> An introduction to Kolmogorov complexity and its applications by Ming Li, P. M. B. Vitányi 1997 0387948686 pages 149–151

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> R. Downey, Some Recent Progress in Algorithmic Randomness in Mathematical foundations of computer science 2004: by Jiří Fiala, Václav Koubek 2004 <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>3-540-22823-3</bdi> page 44

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite id="CITEREFSchnorr1971" class="citation journal cs1">Schnorr, C. P. (1971). "A unified approach to the definition of a random sequence". Mathematical Systems Theory. 5 (3): 246–258. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fbf01694181">10.1007/bf01694181</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:8931514">8931514</a>.</cite>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> Yongge Wang: Randomness and Complexity. PhD Thesis, 1996. <a rel="nofollow" class="external free" href="http://webpages.uncc.edu/yonwang/papers/IPL97.pdf">http://webpages.uncc.edu/yonwang/papers/IPL97.pdf</a>

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <cite id="CITEREFWang1999" class="citation journal cs1">Wang, Yongge (1999). "A separation of two randomness concepts". Information Processing Letters. 69 (3): 115–118. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.199">10.1.1.46.199</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0020-0190%2898%2900202-6">10.1016/S0020-0190(98)00202-6</a>.</cite>

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> Wolfgang Merkle, Kolmogorov Loveland Stochasticity in Automata, languages and programming: 29th international colloquium, ICALP 2002, by Peter Widmayer et al. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>3-540-43864-5</bdi> page 391

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><cite class="citation cs2"><a rel="nofollow" class="external text" href="https://www.encyclopediaofmath.org/index.php?title=Random_sequence">"Random sequence"</a>, <a href="Encyclopedia_of_Mathematics" title="Encyclopedia of Mathematics">Encyclopedia of Mathematics</a>, <a href="European_Mathematical_Society" title="European Mathematical Society">EMS Press</a>, 2001 [1994]</cite></li>

<li><a rel="nofollow" class="external text" href="https://www.youtube.com/watch?v=H2lJLXS3AYM">Video</a> on frequency stability. Why humans can't "guess" randomly</li>

<li><a rel="nofollow" class="external text" href="http://www.ciphersbyritter.com/RES/RANDTEST.HTM#vonNeumann63">Randomness tests by Terry Ritter</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-08-05" href="https://en.wikipedia.org/wiki/?title=Random_sequence&oldid=1304364808">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>